省选集训模拟赛1总结 [rk53/122]
没睡好, RP-- 「伏笔」
三道题分别是:
离距点格
色染图格
数函次二
根据一般人类的排题方式, 靠前的题目显然一般是比较简单的, 所以我先思考了离距点格这道题
题目大概是一个N*M的格点图, 有黑点和白点, 求每个黑点到另一个黑点的最近的欧几里得距离之和, N,M≤3000
第一眼发现自己只会 O(n^4), 想到老师说前两题是NOIP难度, 开始自闭 (bushi)
首先考虑对问题进行转化, 可以发现的是, 有两种路线可以走 :
枚举每个黑色点, 后找到最近的另一个点
从整体入手, 即分治
我认为思路 1 比较好, 那么此时我就无论如何都要考虑每个黑色的点了, 那我的时间复杂度就已经 O(n^2)
在 30 分钟的时候, 我想到了严格 O (n^3) 的做法, 考虑根据行来遍历, 然后假设我们在的点是 (x,y), 那么对于每一列, 最多只有两个点是相对最接近的
对顶栈维护即可
想到了 O(n^3) 的 做法后, 我花了半个小时写出了代码, 然后去想了第二题
大概过了五分钟左右, 我想到了这道题的100分解法, 对于type=0的情况, 必然是所有格点的数量之和减去田字结构的数量, 对于构造,显然可以将格点排序然后直接贪心「伏笔」
大概花了半个小时的时间, 我写了一下这道题的50分的部分分来验证我的猜想
总共过了一个半小时后, 我认为我的猜想是正确的, 因此我提交了我的两份代码, 我之后选择继续思考第一题
在过了半个小时后, 我想到了 O(玄学) 的第一题的做法
考虑在前算法中做出优化, 我们枚举列的时候, 先从近的枚举, 然后在距离足够近的时候, 剪枝即可
我并不清楚时间复杂度, 但是似乎是很好的, 因为 -
当点多的时候, 相对最近距离很快就能找到
到点少的时候, 需要遍历的点就很少
跟着直觉走就好了
直觉会逐渐带领我走向正确答案
我花了半个小时完成了这道题和第二题的编码
因此我决定去看第三题「数函次二」
在读完题的一分钟左右后我大概想到了这道题的思想, 显然维护的是max卷积, 考虑闵可夫斯基和维护二次函数即可
显然问题就是二次函数虽然凸, 但不是离散凸包
仔细思考了半个小时后发现值域很小, 对二次函数进行采样, 在每个dx对二次函数求值即可, 后对于询问, 二分后使用树状数组即可, 对于斜率, 可以考虑求导的思想
然后我就被阴了
我先打了一个暴力
然后发现差不多, 还行, 调试了一会后, 发现题目要求我的答案和标准答案要在小数点后八位数相同
卧槽
然后我就开始卡精度, 大概花了一个半小时调整我的暴力, 使得我的精度在八位数, 但是失败了, 最后大概是在当eps = 1e-12的时候, 精度维持在了七位数
然后我的期望得分是 [?,?,?], 最后得分是 [70,10,0] [rk53]
最后一题精度还是有问题, 第一题被卡常了, 第二题
排序写错了的同时
输出写错了
然后稍微修改了一下, [100,100,0] [rk10]
希望明天吸取教训, 多多检查, 而不是去开新的题目
PS: 最后一题的变态精度已经堪比错题了 (
我就应该在这题大暴力 (